package leetcode_300;

import helpclass.ListNode;

/**
 *@author 周杨
 *PalindromeLinkedList_234  判断一个链表是否是回文
 *describe:反转前面半段链表 开始比较  AC 92%
 *2018年6月24日 下午4:37:45
 */
/**
 *@author 周杨
 *PalindromeLinkedList_234
 *describe:1 快慢指针找到链表中间 2 反转链表 3 顺序遍历判断
 *2018年9月7日 下午2:58:13
 */
public class PalindromeLinkedList_234 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	 public boolean isPalindrome(ListNode head) {
		 ListNode slow=head;  
		 ListNode fast=head;  
		   
		 if(fast==null||fast.next==null)//0个节点或是1个节点  
		     return true;  
		  
		  
		 while(fast.next!=null&&fast.next.next!=null)  
		 {  
		     fast=fast.next.next;  
		     slow=slow.next;  
		 }  
		 //对链表后半段进行反转  
		 ListNode midNode=slow;  
		 ListNode firNode=slow.next;//后半段链表的第一个节点  
		 ListNode cur=firNode.next;//插入节点从第一个节点后面一个开始  
		 firNode.next=null;//第一个节点最后会变最后一个节点  
		 while(cur!=null)  
		 {  
		     ListNode nextNode=cur.next;//保存下次遍历的节点  
		     cur.next=midNode.next;  
		     midNode.next=cur;  
		     cur=nextNode;  
		 }  
		   
		 //反转之后对前后半段进行比较  
		 slow=head;  
		 fast=midNode.next;  
		 while(fast!=null)  
		 {  
		     if(fast.val!=slow.val)  
		         return false;  
		     slow=slow.next;  
		     fast=fast.next;  
		 }  
		 return true;  
	}
}
